package huffmancode;

import java.io.*;
import java.util.*;

public class HuffmanCode {

  public static void main(String[] args) {
    String content = "i like like like java do you like a java";
    byte[] contentBytes = content.getBytes();

//    byte数组长度
//    System.out.println(contentBytes.length);

//    List<Node> bytes = getBytes(contentBytes);
//    System.out.println("nodes:" + bytes);

//    哈夫曼树
//    Node node = createHuffmanTree(bytes);
//    System.out.println("huffman树的前序遍历：");
//    preOrder(node);

//    测试生成的huffman表
//    getCodes(node,"",stringBuilder);
//    System.out.print("huffman编码表:");
//    System.out.println(huffmanCodes);

//
//    byte[] zip = zip(contentBytes, huffmanCodes);
//    System.out.println(Arrays.toString(zip));

    byte[] zip = huffmanZip(contentBytes);
    System.out.println("压缩后的结果：" + Arrays.toString(zip));

    byte[] decode = decode(huffmanCodes, zip);
    System.out.println("原来的结果:" + new String(decode));

    zipFile("C:\\Users\\Administrator\\Desktop\\新建文件夹\\微信图片_20200717180532.png","C:\\Users\\Administrator\\Desktop\\新建文件夹\\test.zip");
    System.out.println("压缩文件成功");

    unzipFile("C:\\Users\\Administrator\\Desktop\\新建文件夹\\test.zip","C:\\Users\\Administrator\\Desktop\\新建文件夹\\2.png");
    System.out.println("文件解压成功");

  }

//  给定一个byte数组，返回压缩后的结果
  public static byte[] huffmanZip(byte[] bytes){
    List<Node> nodes = getBytes(bytes);

//    创建huffman数
    Node huffmanTree = createHuffmanTree(nodes);

//    根据huffman数的头结点生成huffman表
    getCodes(huffmanTree,"",stringBuilder);

    byte[] zip = zip(bytes, huffmanCodes);

    return zip;
  }

  public static List<Node> getBytes(byte[] contentBytes){
    List<Node> list = new ArrayList<>();
//    用map来统计每个字符出现的次数
    HashMap<Byte, Integer> map = new HashMap<>();
    for (byte contentByte : contentBytes) {
      map.put(contentByte,map.getOrDefault(contentByte,0)+1);
    }
//    将map每一个key和value加到list中
    for (Map.Entry<Byte, Integer> entry : map.entrySet()) {
      list.add(new Node(entry.getKey(),entry.getValue()));
    }

    return list;
  }

  public static Node createHuffmanTree(List<Node> list){


    while (list.size() > 1){

      //    从小到大
      Collections.sort(list);

      //    开始处理，取出最小的两个节点，并求出它俩的父节点，然后更新list
      Node leftNode = list.get(0);
      Node rightNode = list.get(1);
      Node parent = new Node(null,leftNode.weight + rightNode.weight);

      parent.left = leftNode;
      parent.right = rightNode;

      list.remove(leftNode);
      list.remove(rightNode);

      list.add(parent);

    }
    return list.get(0);





  }

  public static void preOrder(Node node){
    if (node != null){
      node.preOrder();
    }else {
      System.out.println("huffman树为空");
    }
  }

  /*
  将赫夫曼编码表存放在Map<Byte,String>形式 32->8197->100 100->11000等等[形式]
   */
  static Map<Byte,String> huffmanCodes = new HashMap<>();

//  存放叶子节点的路径
  static StringBuilder stringBuilder = new StringBuilder();

//  获得huffman编码表的方法
  private static void getCodes(Node node,String code,StringBuilder stringBuilder){
    StringBuilder stringBuilder2 = new StringBuilder(stringBuilder);
    stringBuilder2.append(code);

    if (node != null){
      if (node.data == null){
        getCodes(node.left,"0",stringBuilder2);
        getCodes(node.right,"1",stringBuilder2);
      }else {
        huffmanCodes.put(node.data,stringBuilder2.toString());
      }
    }
  }

//  数据压缩的方法
  private static byte[] zip(byte[]bytes,Map<Byte,String> huffmanCodes){

    StringBuilder stringBuilder = new StringBuilder();

    for (Byte ele : bytes) {
      stringBuilder.append(huffmanCodes.get(ele));
    }
//    System.out.println(stringBuilder);
    int len = 0;
    if (stringBuilder.length() % 8 ==0){
      len = stringBuilder.length() / 8;
    }else {
      len = stringBuilder.length() / 8 + 1;
    }
    byte[] huffmanCodeBytes = new byte[len];

    int index = 0;

    for (int i = 0; i < stringBuilder.length(); i= i + 8) {
      String strByte;
      if (i + 8 > stringBuilder.length()){
        strByte = stringBuilder.substring(i);
      }else {
        strByte = stringBuilder.substring(i,i + 8);
      }
      huffmanCodeBytes[index] = (byte) Integer.parseInt(strByte,2);
      index++;
    }
    return huffmanCodeBytes;
  }

  private static String byteToBitString(boolean flag,byte bytes){

    int temp = bytes;
    if (flag){
      temp = temp | 256;//如果是正数，需要补高位
    }
    String str = Integer.toBinaryString(temp);
    if (flag){
      return str.substring(str.length() - 8);
    }else {
      return str;
    }
  }

  private static byte[] decode(Map<Byte,String> huffmanCodes ,byte[] huffmanBytes){

    StringBuilder stringBuilder = new StringBuilder();
    for (int i = 0; i < huffmanBytes.length; i++) {
      byte b = huffmanBytes[i];
      boolean flag = (i == huffmanBytes.length - 1);
      stringBuilder.append(byteToBitString(!flag,b));
    }
//    System.out.println("huffman字节数组对应的二进制数组：" + stringBuilder.toString());

    HashMap<String, Byte> map = new HashMap<>();
    for (Map.Entry<Byte, String> entry : huffmanCodes.entrySet()) {
      map.put(entry.getValue(),entry.getKey());
    }

    List<Byte> list = new ArrayList<>();

    for (int i = 0; i < stringBuilder.length();) {
      int count = 1;
      boolean flag = true;
      Byte b = null;

      while (flag){
        String key = stringBuilder.substring(i,i + count);
        b = map.get(key);
        if (b == null){
          count++;
        }else {
          flag = false;
        }
      }
      list.add(b);
      i = i + count;
    }

    byte[] b = new byte[list.size()];
    for (int i = 0; i < b.length; i++) {
      b[i] = list.get(i);
    }

    return b;
  }

//  压缩文件的方法
  private static void zipFile(String srcFile,String dstFile){

    FileInputStream is = null;
    FileOutputStream os = null;
    ObjectOutputStream oos = null;

    try {
      is = new FileInputStream(srcFile);
      byte[]b = new byte[is.available()];
      is.read(b);

//      对文件压缩
      byte[] huffmanZip = huffmanZip(b);

//      创建文件的’出淡，存旅压缩文件
      os= new FileOutputStream(dstFile);
//    创建一个和文件输出流关联的ObjectOutputStream
      oos = new ObjectOutputStream(os);
//    把赫夫强编码后的字符数组写入压缩文件
      oos.writeObject(huffmanZip);
//    为了恢复文件使用，一定要把huffman编码表写进去
      oos.writeObject(huffmanCodes);

    } catch (Exception e) {
      e.printStackTrace();
    }finally {
      try {
        is.close();
        os.close();
        oos.close();
      } catch (IOException e) {
        e.printStackTrace();
      }
    }
  }

//  文件解压的方法
  private static void unzipFile(String srcFile,String dstFile){

    FileInputStream is = null;
    ObjectInputStream ois = null;
    FileOutputStream os = null;

    try {
      is = new FileInputStream(srcFile);
      ois = new ObjectInputStream(is);

      //byte数组huffmanBytes
      byte[]huffmanBytes = (byte[])ois.readObject();
      //读取huffman编码表
      Map<Byte,String>huffmanCodes = (Map<Byte,String>)ois.readObject();

//      原始数组
      byte[] bytes = decode(huffmanCodes, huffmanBytes);

      os = new FileOutputStream(dstFile);

      os.write(bytes);

    } catch (Exception e) {
      e.printStackTrace();
    }finally {
      try {
        os.close();
        ois.close();
        is.close();
      } catch (IOException e) {
        e.printStackTrace();
      }
    }


  }

}

class Node implements Comparable<Node>{

  Byte data;//存放数据本身 如：a-》97
  Node left;
  Node right;
  int weight;//权值,即字符出现的次数

  public Node(Byte data, int weight) {
    this.data = data;
    this.weight = weight;
  }

  @Override
  public String toString() {
    return "Node{" +
            "data=" + data +
            ", weight=" + weight +
            '}';
  }

//  从小到大
  @Override
  public int compareTo(Node o) {
    return this.weight - o.weight;
  }

//  前序遍历
  public void preOrder(){
    System.out.println(this);
    if (this.left != null){
      this.left.preOrder();
    }
    if (this.right != null){
      this.right.preOrder();
    }
  }
}